package com.magupe.develop.binary.tree;

import java.util.*;

/**
 * 二叉树
 *
 * @author maguangpeng
 */
public class BinaryTree<T> {

    private BinaryTreeNode<T> root;

    public BinaryTree() { }

    public void createTree(Object[] objs) {
        List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>();
        for (Object object : objs) {
            nodes.add(new BinaryTreeNode(object));
        }
        this.root = nodes.get(0);
        // 第一次循环，0指向1和2
        nodes.get(0).left = nodes.get(1);
        nodes.get(0).right = nodes.get(2);
        // 第二次循环，1指向3和4
        nodes.get(1).left = nodes.get(3);
        nodes.get(1).right = nodes.get(4);
        // 第三次循环，2指向5和6
        nodes.get(2).left = nodes.get(5);
        nodes.get(2).right = nodes.get(6);
        // 第四次循环，3指向7和8
        nodes.get(3).left = nodes.get(7);
        nodes.get(3).right = nodes.get(8);
        // 第五次循环，4指向9和10
        nodes.get(4).left = nodes.get(9);
        nodes.get(4).right = nodes.get(10);
        // 第六次循环，5指向11和12
        nodes.get(5).left = nodes.get(11);
        nodes.get(5).right = nodes.get(12);
        // 第器次循环，6指向13和14
        nodes.get(6).left = nodes.get(13);
        nodes.get(6).right = nodes.get(14);

        // 循环实现
        nodes = new ArrayList<BinaryTreeNode>();
        for (Object object : objs) {
            nodes.add(new BinaryTreeNode(object));
        }
        this.root = nodes.get(0);
        int len = 15/2;
        len = 7;
        for (int i = 0; i < len; i++) {
            nodes.get(i).left = nodes.get(i * 2 + 1);
            /**
             * new Object[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
             * (i * 2 + 2) 最大值14
             * 避免越界，14小于15，但是14不小于14
             */
            if ((i * 2 + 2) < nodes.size()) {
                nodes.get(i).right = nodes.get(i * 2 + 2);
            }
        }
    }

    /**
     * 先序遍历
     *
     * @param root
     */
    public void preOrder(BinaryTreeNode root) {
        if (root != null) {
            System.out.println(root.getData());
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    /**
     * 先序遍历(非递归)
     *
     * @param root
     */
    public void iterativePreOrder(BinaryTreeNode root) {
        if (root != null) {
            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            while (!stack.empty() || root != null) {
                while (root != null) {
                    System.out.println(root.getData());
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                root = root.right;
            }
        }
    }

    /**
     * 中序遍历
     *
     * @param root
     */
    public void inOrder(BinaryTreeNode root) {
        if (root != null) {
            inOrder(root.left);
            System.out.println(root.getData());
            inOrder(root.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param root
     */
    public void afterOrder(BinaryTreeNode root) {
        if (root != null) {
            afterOrder(root.left);
            afterOrder(root.right);
            System.out.println(root.getData());
        }
    }

    /**
     * 按层遍历
     *
     * @param root
     */
    public void levelOrder(BinaryTreeNode root) {
        if (root != null) {
            // 1.首先将二叉树的根节点push到队列中
            Queue<BinaryTreeNode> queue = new LinkedList<>();
            queue.add(root);
            // 2.while循环
            while (!queue.isEmpty()){
                // 3.输出队头的元素
                BinaryTreeNode current = queue.poll();
                System.out.println(current.getData());
                // 4.判断节点如果有孩子，就将孩子push到队列中
                if(current.left != null) {
                    queue.offer(current.left);
                }
                if(current.right != null) {
                    queue.offer(current.right);
                }
            }
        }
    }

    public static void main(String[] args) {
        Object[] numbers = new Object[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        BinaryTree<Integer> tree = new BinaryTree<Integer>();
        tree.createTree(numbers);
        tree.levelOrder(tree.root);
    }
}
